package recursion;

import java.util.Arrays;

//全排列(n个数有多少种排列组合方式)
public class FullPermutation {
    public static void main(String[] args) {
        int[] a= {1,2,3,4};
        f(a);

    }

    private static void f(int[] a){
        f(a,0);
    }

    /*
        最简问题：start在末尾，直接打印数组中的排列
        1.循环i从start到末尾
        2.i和start交换
        3.对start+1开始的范围，递归进行全排列
        4.i和start交换(恢复原来的位置)
     */

    private static void f(int[] a,int start){
        if (start==a.length-1){
            System.out.println(Arrays.toString(a));
            return;
        }
        for (int i=start;i<a.length;i++){
            swap(a,i,start);
            f(a,start+1);
            swap(a,i,start);
        }
    }

    private static void swap(int[] a,int i ,int start){
        int t = a[i];
        a[i] = a[start];
        a[start] = t;
    }
}
